#include <string>
#include <sstream>
#include "GraphLoader.h"

void GraphLoader::genTestDAG( Graph& g, float density, int size, int fanout ) {
	g.clear();	
	vector<Vertex> nodes;
	list<Vertex> queue;
	int i;
	int edge_num = (int)(density*size); // total edges

	//for debug
	//cout << "edge_num: "<< edge_num << endl;
	
	// add all nodes
	for( i = 0; i < size; ++i ) {
		nodes.push_back( add_vertex( g ) );
		g[ nodes[i] ].id = i;
	}
	
	// generate all edges
	// first, generate a tree
	const int STOPRATE = 2;
	int MAXCHILD = fanout;
	int num_child = rand() % MAXCHILD;
	bool has_edge;
	Vertex v;
	Edge e;
	g[ nodes[0] ].level = 0; // root is level 0
	queue.push_back( nodes[0] ); // put the root into queue
	for( i = 1; i < size; ++i ) {
		// debug
		//cout << "i: " << i << "  num_child: " << num_child;
		
		// add a tree edge
		v = queue.front();
		
		// debug
		//cout << " top: " << g[v].id << endl;
		
		tie( e, has_edge ) = edge( v, nodes[i], g );
		if( !has_edge ) {
			tie(e, has_edge) = add_edge( v, nodes[i], g );
			
			g[e].tree = true;
			g[ nodes[i] ].level = g[v].level + 1; // add a level
			
			num_child--;
		}else{
			assert( false );
		}
		
		// make some nodes not to have children
		if( rand() % 10 >= STOPRATE ) {
			queue.push_back( nodes[i] );
		}
		
		if( num_child <= 0 ) {		
			if( queue.size() > 1 ) {
				queue.pop_front();
			}
			
			// update the number of children for the next node
			num_child = rand() % MAXCHILD;
		}
		
	}
	
	// for debug
	//print_graph( g, get( &VertexProp::id, g ) );
	
	// second, randomly generate other edges
	edge_num -= size - 1;
	int x, y;
	Vertex u, w;
	while( edge_num > 0 ) {
		x = rand() % size;
		y = rand() % size;
		if( x == y ) {
			continue;
		}
		
		u = nodes[x];
		w = nodes[y];
		
		// from smaller level to larger level
		if( g[u].level < g[w].level || 
			(g[u].level == g[w].level && x < y ) ) {
			tie( e, has_edge ) = edge( u, w, g );
			if( !has_edge ) {
				tie(e, has_edge) = add_edge( u, w, g );
				g[e].tree = false;
			}
		}else{
			tie( e, has_edge ) = edge( w, u, g );
			if( !has_edge ) {
				tie(e, has_edge) = add_edge( w, u, g );
				g[e].tree = false;
			}
		}
		
		--edge_num;
	}
	
	// for test merge strongly connected components
//	for( int j = 0; j < 50; ++j ) {
//		x = rand() % size;
//		y = rand() % size;
//		if( x == y ) {
//			continue;
//		}
//		
//		u = nodes[x];
//		w = nodes[y];
//		
//		tie( e, has_edge ) = edge( u, w, g );
//		if( !has_edge ) {
//			tie(e, has_edge) = add_edge( u, w, g );
//			g[e].tree = false;
//		}
//	}	
}

void GraphLoader::writeGraph( std::ostream& out, Graph& g ) {
	
	out << "graph_for_greach" << endl;
	out << num_vertices( g ) << endl; // first line: vertex size
	
	Vertex v;
	graph_traits<Graph>::vertex_iterator vi, vi_end;
	graph_traits<Graph>::out_edge_iterator eo, eoend;
			
	for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
		out << g[*vi].id <<": ";
		// output the outgoing edges
		for( tie(eo, eoend) = out_edges( *vi, g ); eo != eoend; ++eo ) {
			v = target( *eo, g );
			out << g[v].id << " ";
		}
		//out << endl;	
		out << "#" << endl;
	}
}

void GraphLoader::readGraph( std::istream& in, Graph& g ) {
	string buf;
	getline( in, buf );	
	if( buf != "graph_for_greach" ) {
		cout << "BAD FILE FORMAT!" << endl;
		exit( 0 );
	}
	int n;
	getline( in, buf );
	istringstream( buf ) >> n;
	vector<Vertex> nodes(n);
	for(int i = 0; i < n; ++i ) {
		nodes[i] = add_vertex( g );
		g[ nodes[i] ].id = i;
	}
	string sub;
	int idx;
	int sid = 0; // source
	int tid;
	while( getline( in, buf ) ) {
		idx = buf.find(":");
		buf.erase( 0, idx+2);
		while( buf.find(" ") != string::npos ) {
			sub = buf.substr( 0, buf.find(" ") );
			istringstream( sub ) >> tid;
			buf.erase(0, buf.find(" ")+1);
			
			add_edge( vertex( sid, g ), vertex( tid, g ), g );
		}
		
		++sid;
	}
	
//	print_graph( g, get( &VertexProp::id, g ) );
}
